Programmable logic devices (PLDs) are a well-known type of digital integrated circuit that can be programmed to perform specified logic functions. One type of PLD, the field programmable gate array (FPGA), typically includes an array of configurable logic blocks (CLBs) and programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a programmable interconnect structure. Some FPGAs also include additional logic blocks with special purposes (e.g., DLLs, RAM, and so forth).
The interconnect structure typically includes a large number of routing resources such as interconnect lines (e.g., metal wires) running generally horizontally and vertically between the various logic blocks, and programmable interconnect points (PIPS) that selectively couple the interconnect lines to each other and to input and output pins of the logic blocks. Interconnect lines can span, for example, one CLB, two CLBs, six CLBS, half of the chip, and so forth. By enabling selected PIPs, two signals in two logic blocks can be interconnected via one or more of the interconnect lines.
The interconnect structure, CLBs, IOBs, and other logic blocks are typically programmed by loading a stream of configuration data into internal configuration memory cells that define how the interconnect structure and logic blocks are configured. The configuration data can be read from memory (e.g., an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA. Thus, the process of implementing a user circuit in an FPGA essentially amounts to the production of a configuration data file that will elicit the desired behavior from the FPGA.
The design implementation process involves a well-known series of steps, which are illustrated in FIG. 1. In step 101, a design file is created that includes a description of the elements included in the user circuit and how these elements are connected. The design file can be, for example, a file including a description of a schematic drawing or a file in HDL (Hardware Description Language) format. In step 102, the design file is converted (e.g., by a synthesis tool) to a netlist in a format understandable by the FPGA implementation tools. (A “netlist” is a description of a circuit comprising a list of low-level circuit elements or gates and the connections (nets) between these elements.) For example, FPGA implementation tools provided by Xilinx, Inc. accept netlist files in EDIF (Electronic Design Interchange Format) format.
In step 103, the FPGA implementation tools partition the elements recited in the netlist into groups of logic that will fit into the resources available in the FPGA. For example, a group of logic gates having up to four common input signals and a single output signal can be partitioned into a group of logic that will fit into a single 4-input lookup table.
The next step (step 104) is to place the partitioned elements into particular locations in the FPGA, e.g., into a specific configurable element of a specific CLB. The location assigned to each partitioned element can be, for example, randomly assigned and then gradually improved by swapping the placements and evaluating the results (step 105). The desirability of a particular placement can be graded based on several factors. One of these factors is the estimated speed of the design that will result after the next step (step 106), which is routing the interconnections between the various logic blocks. The routing step also typically involves a great deal of optimization. The final step, step 107, is to generate a configuration data file from the routed design.
Clearly, the actual speed of an implemented design is not known until after the routing step has been performed. However, the speed of interconnection paths between logic elements is often critical. Routing delays often determine the maximum operating frequency of a circuit. Therefore, during the placement optimization process (step 105) it is desirable to obtain the best possible estimate of routing delays consistent with the required software execution time.
The most accurate method of estimating a routing delay would be to actually route the design and then measure the delays using the timing analysis software that is readily available for routed FPGA designs. However, the estimation of routing delays might need to be performed thousands of times during the placement of a single design, and routing is a computationally intensive task that can be very time-consuming. Therefore, it is necessary to use faster techniques for estimating the routing delays of a particular prospective placement. However, it is also necessary to estimate the routing delays accurately, so the placement optimization process will result in a high-quality placement of the design, i.e., a placement that will operate at the desired frequency.
The method typically used to estimate routing delays during the placement optimization process is to generate a function for the estimated delay, as follows:Est. Delay=function(dx,dy,congestion,fanout)where dx and dy are the distance in FPGA tiles from the source pin to the load pin for the connection for which the delay is being estimated. The value for congestion in the equation is a numerical measure of the congestion of nets in the area where the connection under consideration is being routed. The value for fanout in the equation is the fanout (i.e., the number of loads) of the net of which the connection is a part.
Typically, the estimated delay function is derived in an empirical fashion, by placing and routing several designs and measuring the delays. The function is then computed, usually by linear or non-linear regression, that most closely fits the distribution of the routing delays.
However, this known method of delay estimation has its drawbacks. There is generally a wide variation in the routing delays used to compute the function. Indeed, some FPGAs are now deliberately designed to provide a mixture of slow and fast interconnect. The slow interconnect is used for nets that are not speed-critical, and offers the advantage of using less surface area, e.g., it is not necessary to buffer these interconnect lines. The fast interconnect offers increased speed at the cost of consuming more surface area of the FPGA. Therefore, while a function calculated using average delays is indeed accurate on average, the function can be significantly inaccurate for any given connection.
Therefore, it is desirable to provide improved methods for estimating routing delays in an FPGA design implementation prior to actually routing the design.